package com.example.shirotest.study;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class MergeSort {

    //归并算法
    public static void main(String[] args) {
        //int arr[]  = {8,4,5,7,1,3,6,2,0,234};
        //int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        //mergeSort(arr,0,arr.length-1,temp);

        //System.out.println("The result is : " + Arrays.toString(arr));
        //printArray(arr);

        spendTimeTest();
    }

    //比较不同排序方式的速度
    private static void spendTimeTest(){
        int arrSize = 8000000;
        int[] arr = new  int[arrSize];
        for (int i = 0; i < arrSize; i++) {
            arr[i] = (int) (Math.random() * 8000000); //生成一个[0,8000000]的数
        }

        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateStr = simpleDateFormat.format(date);
        System.out.println("Before time : " + dateStr);

        //归并排序
        int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        mergeSort(arr,0,arr.length-1,temp);

        Date date2 = new Date();
        String dateStr2 = simpleDateFormat.format(date2);
        System.out.println("After  time : " + dateStr2);
    }


    //打印数组
    private static void printArray(int[] ary){
        for (int anInt : ary) {
            System.out.printf("%d ",anInt);
        }
    }

    //分解 + 合并
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int mid = (left + right) / 2; //中间索引
            //向左递归进行分解
            mergeSort(arr,left,mid,temp);
            //向右递归进行分解
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }


    //合并方法
    /**
     * @param arr  排序的原始数组
     * @param left 左边有序序列的初始索引
     * @param mid  中间索引
     * @param right 右边索引
     * @param temp  中转数组
     */
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;  //初始化i,左边有序序列的初始索引
        int j = mid+1; //初始化j,右边有序序列的初始索引
        int t = 0;     //指向temp数组的当前索引

        //步骤1
        //先把左右两边的数据按照规则填充到temp数组中
        //直到左右两边的有序序列，有一边处理完毕为止

        while (i<=mid && j<=right){
            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素

            //即将左边的当前元素，填充到temp数组
            //然后 t++ , i++
            if(arr[i] <= arr[j]){
                temp[t] = arr[i];
                t++;
                i++;
            }else {  //反之，将右边的有序序列当前元素，填充到temp数组
                temp[t] = arr[j];
                t++;
                j++;
            }
        }


        //步骤2
        //把有剩余数据的一边数据依次全部填充到temp
        while (i <= mid){
            temp[t] = arr[i];
            t++;
            i++;
        }

        while (j <= right){
            temp[t] = arr[j];
            t++;
            j++;
        }


        //步骤3
        //将temp数组的元素拷贝到arr
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right){
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }

    }

}
